Batch 2 - Class 05 - Logic (Truthtellers and liars)

Last Class Homework:

Homework: Place Eight queens on a chessboard, so that none of them can capture each other.
Homework: Find the winning strategy for the following game. There are 15 coins in a row. Each player can pick 1, 2 or 3 adjacent coins in her turn. Note that two coins from between which a coins has been removed do not count as adjacent. Then the next player does the same, and so on. Does the first player have a winning strategy? If so, what is it?
Answer: Pick the middle coin to leave two rows of 7 coins each. Now replicate whatever move the opponent makes to preserve symmetry after every more.
Instructor Notes: Draw a parallel to the left/down move game on a chessboard

Attendance Smiti, Ishartek, Tishyaa, Armaan, Simran, Hriday, Aastha, Avy, Kushaan, Tara, Adit, Diya, Muskaan, Anisha, Diya, Varun

Class puzzles

Introduce the notion of Truthtellers and Liars as per MC Diaries, Page 26

MC Diaries Y1, Chap 2 - Problem 2: While visiting the Knights and Liars Island, you meet a boy who tells you that he is a liar. Does he live on the island or is he a tourist?
Answer: Both knights and liars would claim that they are truthtellers, hence the boy is a tourist
MC Diaries Y1, Chap 2 - Problem 3: Two island boys, Sam and Bob, are introducing themselves to you. Sam says, "At least one of us is a liar." Who is what?
Answer: If Sam is a liar, then he is telling the truth (that at least one of them is a liar), which is not possible. Hence Sam must be a truthteller. Since there has to be at least one liar, that must be Bob

Instructor Notes: Introduce the notion that such problems have finite number of possibilities, and one way to solve is to "test" for all possibilities, and see which one works.

MC Diaries Y1, Chap 2 - Problem 5: While visiting the island, you meet a group of three islanders: Tom, George and Betty. You ask each of them the same question: "How many knights are in your group?" Tom replies, "None." George says, "One." Can you find out what Betty is? What is her answer?
Answer: First observation is that Tom is a liar. If he were a knight, he would not claim that there are no knights. If George's claim that there is only one knight is true, then George must be that knight, and Betty must be a liar. If George's claim is false, then there aren't zero/one knights, which cant be true. So Betty is a liar, and she can answer anything other than one.
MC Diaries Y1, Chap 4 - Problem Set Problem 1: While visiting the island of knights and liars, you meet a local boy. What should you ask him if you want to find out whether he is a knight or a liar?
Annwer: Any common knowledge question - "Are you a girl", "Is moon larger than earth"
MC Diaries Y1, Chap 3 - Problem 3: While visiting the knights and liars island, you meet james and peter. James tells you that at least one of the two is a liar. Who is what?
Answer: Its not possible that James is a liar, because then his statement is correct. So James is a knight, and Peter liar
MC Diaries Y1, Chap 3 - Problem 5: (Introduce notion of Tourist) - While visiting the Knights and Liars island, you come to a party. Every single person in the party tells you that there are some liars in the room. What is really happening?
Answer: None of the people there can be liars, because then that liar would be telling the truth. Given that no one can be a liar, no one can be a truthteller because then they would be lying. So all are tourists
MC Diaries Y1, Chap 3 - Problem 7: There are two villages, one with all Knights and one with all Liars, but they often visit each others' village. As a tourist, ask one question to the first person you meet, to figure out if you are in the Knights village or the Liars village.
Answer: "Do you live in this village"

Instructor Notes: This is a complex puzzle. Kids might need the understanding that while there are four possibilities (of whether a truthteller or liar is being asked, and which village one is in), we are allowed only one Yes/No question. So we can't disambiguate all for possibilities. This means that we will not know whether the person is a liar or truthteller, and hence the question has to be such that whether its the truthteller or a liar, they answer the same, given the identity of the village.

Homework: Khan Academy, Liar Truthteller brain teaser - 2 doors, one has treasure, one has hell. Two door keepers, one always tells truth, the other always lies. One question to one doorkeeper to decide which door to open.
Answer: "what would the other guy say which is the correct door to open"
Homework: (Contributed by Tara) Truthtellers and liars. There is a village of truthtellers (who always tell the truth) and liars (who always lie). I want to go to the village and reach a fork in the road, where a villager is standing. Can I ask one question to the villager, without knowing whether she is a truthteller or a liar, which will allow me to determine which path to take on the fork to reach the village
Answer 1: "If I asked you which road goes to the village, what would you say?" (Take the road the villager points to. Logic is Truth->Truth = Truth, and Lie->Lie = Truth)Answer 2: "If I asked a member of your opposite tribe the road to the village, what would they say?" (Take the road the villager does not point to. Logic is Truth->Lie = Lie, and Lie->Truth = Lie)
Homework: MartinShCol 5.22: four bugs at corner of squares start moving directly towards each other. Trace their path. How long does each bug travel before they meet
Answer: Spiral converging at centre. Distance is side of square

References: Mathematical Circle Diaries, Year 1, by Anna Burago

The Colossal Book of Short Puzzles and Problems, by Martin Gardner

https://www.khanacademy.org/math/recreational-math/puzzles/brain-teasers/v/liar-truthteller-brain-teaser